package com.hardy.leetcode;

import java.util.ArrayList;

/**
 * Created by 1340760685@qq.com on 2016/9/25.
 */
public class Nqueens {
    public static ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> res = new ArrayList<>();
        String[] s = new String[n];
        int[] A = new int[n+1];
        dfs(1, A, res, s);
        return res;
    }

    private static void dfs(int n, int[] A, ArrayList<String[]> res, String[] s) {
        if (n >= A.length) {
            res.add(s.clone());
        } else {
            for (int j = 1; j < A.length; j++) {
                if (check(A, n, j)) {
                    A[n] = j;
                    StringBuilder sb = new StringBuilder();
                    for (int i = 0; i < A.length-1; i++) {
                        if (i == j-1) {
                            sb.append("Q");
                        } else {
                            sb.append(".");
                        }
                    }
                    s[n - 1] = sb.toString();
                    dfs(n + 1, A, res, s);
                }
                A[n] = 0;
            }
        }
    }

    private static boolean check(int[] a, int n, int j) {
        for (int i = 1; i < n; i++) {
            if (j == a[i] || Math.abs(n - i) == Math.abs(j - a[i])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ArrayList<String[]> res = solveNQueens(8);
        for(String[] str:res){
            for(int i=0;i<str.length;i++){
                System.out.println(str[i]);
            }
            System.out.println();
        }
    }
}
